import java.util.*;

public class demo1 {
    //注意边界情况
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> lists=new ArrayList<>();
        Queue<TreeNode>queue=new LinkedList<>();
        if(root==null)return lists;
        queue.add(root);
        int flag=1;
        while (!queue.isEmpty()){
            int temp=queue.size();
            flag=-flag;
            List<Integer>list=new ArrayList<>();
            int []arr=new int[temp];
            for(int i=0;i<temp;i++){
                TreeNode treeNode=queue.poll();
                if(treeNode!=null)
                arr[i]=treeNode.val;
                if(treeNode.left!=null)
                queue.add(treeNode.left);
                if(treeNode.right!=null)queue.add(treeNode.right);
            }
            if(flag==-1){
                for(int i=0;i<temp;i++)list.add(arr[i]);
            }else{
                for(int i=temp-1;i>=0;i--)list.add(arr[i]);
            }
            lists.add(list);
        }
        return lists;
    }
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }
}
